#include "main/utils.h"
using namespace std;

vector<int> findSumS(const vector<int> &vec, const int &sum) {
  int begin = 0;
  int end = vec.size() - 1;
  vector<int> ret;
  while (begin < end) {
    int sum_tmp = vec[begin] + vec[end];
    if (sum_tmp == sum) {
      ret.push_back(vec[begin]);
      ret.push_back(vec[end]);
      return ret;
    } else if (sum_tmp < sum) {
      ++begin;
    } else {
      --end;
    }
  }
  return {};
}

vector<vector<int>> findSeqSumS(const int &sum) {
  vector<vector<int>> ret_seqs;
  vector<int> tmp_seq = {1, 2};
  int cur_sum = 3;
  int cur_num = 3;
  while (tmp_seq.size() > 1) {
    if (cur_sum == sum) {
      ret_seqs.push_back(tmp_seq);
      cur_sum -= tmp_seq[0];
      tmp_seq.erase(tmp_seq.begin());
    } else if (cur_sum < sum) {
      tmp_seq.push_back(cur_num);
      cur_sum += cur_num;
      ++cur_num;
    } else {
      cur_sum -= tmp_seq[0];
      tmp_seq.erase(tmp_seq.begin());
    }
  }
  return ret_seqs;
}

int main() {
  vector<int> vec = {1, 2, 4, 7, 11, 15};
  int sum = 15;
  vector<int> ret = findSumS(vec, sum);
  cout << "Two number which their sum is 15: " << ret[0] << " " << ret[1] << endl;

  vector<vector<int>> ret_vecs = findSeqSumS(sum);
  for (int i = 0; i < ret_vecs.size(); ++i) {
    printVec("seq", ret_vecs[i]);
  }

  return 0;
}
